In 1984, Shamir proposed some schemes (an identity-based signature and encryption scheme) in the article “Identity-based cryptosystems and signature schemes” published at Crypto 84) based on the fact that a user's public key is directly related to the person's identity (for example his name, email address etc.). However, no mathematical tool could resolve the problems raised at the presentation of this research. Up to 2001, no instantiation of such a scheme had been found. At the Crypto 01 conference, Boneh & Franklin set up the first protocol, using special mathematical functions, namely pairings described in “Identity-Based Encryption from the Weil Pairing”. These functions were initially used to carry out attacks (MOV and then FR attacks) on cryptosystems using elliptic curves with a low embedding degree, especially supersingular curves because the pairings make it possible to reduce the discrete logarithm problem defined on an elliptic curve to the discrete logarithm problem defined on a multiplicative group of a finite field where there is a sub-exponential algorithm available that can be used to resolve this problem in certain cases. Boneh & Franklin used these functions to obtain a concrete example (concrete both from the security viewpoint and from the practical viewpoint (at the implementation level)) of an identity-based encryption scheme. They achieved this instantiation by using a Weil pairing and, since then, many other types of pairings (Tate pairing, Ate pairing and Eta pairing) and schemes (encryption, signature, key exchange) have been proposed using these tools.
It must be noted that these schemes need to use a special hash function through which a point on an elliptic curve can be made to correspond to a given binary sequence (i.e. a succession of 0's and 1's). For example, in the article mentioned here above: “Identity-Based Encryption from the Weil Pairing”, the MapToPoint function is used to convert a binary sequence (and identifier) into a point of the curve having a given order.
It must be noted that the group of an elliptic curve over a finite field is either cyclic or the product of two cyclic groups. It can be noted that when the cardinal of the set of points of the curve E, denoted as #E(GF(pn), is a prime number, then the set of points of E forms a cyclic group and therefore all the points (except the point at infinity) are generators of the group E. Thus, a function making a binary sequence correspond to any point of the curve (other than the point at infinity) actually makes it possible to obtain a generator point of the group and this point therefore has the desired property. There are many techniques for building prime order curves (for example cf. Schmidt et al, “Generating Elliptic Curves of Prime Order”, CHES, 2001, and Barreto et al. “Pairing-Friendly Elliptic Curves of Prime Order” SAC conference 2005).
It can be noted that the use of hash functions or conversion functions is found in other schemes (where the binary sequence represents a message or a password): the BLS signature scheme (cf. Boneh et al, “Short Signatures from the Weil Pairing”, Asiacrypt 2001 conference), the SPEKE (Simple Password Exponential Key Exchange) protocol which is a zero-knowledge proof algorithm using the sharing of a password, enables the exchange of keys between two parties, (CF IEEE P1363.2 standard), the PEKS protocol (“Password Encryption Key”, where a password or other identifying data is converted into points of a curve) as well as in the multiple-signature and aggregate-signature schemes.
In other schemes, it is not an identifier that has to be converted but a message (i.e. there are no constraints this time bearing on the order of the generated point). For example, the cryptosystem known as the Massey-Omura cryptosystem (U.S. Pat. No. 4,567,600), adapted to elliptic curves requires the use of such a function: indeed, when a message m is encrypted, the first step is that of representing this message m as a point M of the curve used.
In the prior art, there are several solutions to instantiating such hash functions (which are different from the MapToPoint function already referred to).
A first technique, which is a probabilistic technique, uses the following method proposed by Koblitz (set forth in W. Trappe et al, “Introduction to Cryptography with Coding Theory”, chapter 16): given the elliptic curve E defined by the simplified Weirstrass equation y2=x3+a·x+b defined over a finite field GF(p), with p being a prime number strictly greater than three, the method comprises the following steps:
1. Express the message m as an element m, of the field GF(p). It may be noted that the probability that the element mi3+a·mi+b has a square root modulo p is ½.
2. Choose an integer k such that (mi+1)·k<p
3. For j from 0 to k−1,                compute xj:=mi·k+j mod p,        
Test to see whether zj:=xj3+a·xj+b possesses a square root modulo p; as soon as an element zj possesses a square root modulo p, the execution of the loop is stopped.
4. If j<k, then compute yj a square root of zj modulo p and make the point (xj, yj) correspond to the message m. If not, it is not possible to make a point belonging to the elliptic curve E correspond to this message m.
Thus, the probability that this algorithm will not find any correspondence between a message m and a point on the curve E is ½k.
This algorithm can be adapted to finding a correspondence between a message and a point on an elliptic curve defined over a finite field GF(pn). A description of this algorithm can be found in the article by Muralidhara et al “A Result on the Distribution of Quadratic Residues with Applications to Elliptic Curve Cryptography”, Indocrypt conference 07.
A second technique, which is also probabilistic, is presented in the document D1 corresponding to the article by P. Barreto et al., “Fast hashing onto elliptic curves over fields of characteristic 3”, which mentions two hash functions (the Map2Grouph and Map3Grouph functions), used to set up a correspondence, from a given elliptic curve defined over the finite field GF(3n), between any message m and a point M of this elliptic curve.
However, it can be noted that these techniques are sensitive to covert channel attacks (especially timing attacks carried out during the execution of these algorithms). This is because that these hash functions do not have a constant running time for, in each of these algorithms, there is a step for resolving an equation (a quadratic equation at the step 4 for the Map2Grouph function and a cubic equation at the step 4 for the Map3Grouph function) which does not necessarily allow for a solution. The algorithms reiterate the steps 2 to 4 so long as the equation does not accept any solution, which is the reason for the non-uniformity of execution in terms of time.
Several techniques have been proposed to mitigate this problem of non-uniformity in the running time of such a hash function. In particular, the first technique was proposed in the document D2, corresponding to the article by Shallue et al., “Construction of rational points on elliptic curves over finite fields” ANTS Conference 06, which uses Skalba's equality as well as a modification of the Tonelli-Shanks algorithm (used to extract square roots in a finite field). This algorithm has a complexity (in terms of running time) in O(log3pn), when pn=3 mod 4, and if not in O(log4pn) where the pairs (p,n) do not verify the above equality with p being a prime number strictly greater than 3.
The document D3, corresponding to the article by T. Icart, “How to hash into elliptic curves”, CRYPTO Conference 09, proposes a second technique for building a hash function out of an elliptic curve defined over GF(pn) comprising a step for associating elements of GF(pn) with points belonging to the elliptic curve E, in deterministic time, with a complexity in O(log3pn), when pn=2 mod 3 (thus, this technique can be applied to a bigger family of curves). In the document D4, corresponding to the article by Farashahi et al., “On Hashing into Elliptic Curves” in the “Journal of Mathematical Cryptology” December 2009, as well as in the document D5, corresponding to the article by Coron et al., “An indifferentiable hash function into elliptic curves” IACR, 2009, and the document D6, corresponding to the article by Fouque et al. “Estimating the size of the image of deterministic hash functions to elliptic curves” IACR eprint site 2010, the conjecture of the asymptotic formula introduced in the document D3 is refined and proven through the use of Chebotarev's density theorem. These documents therefore bring no relative improvement to the hash function building technique as such.
It may be noted that the deterministic hash functions of the documents D2 and D3 cannot be used to make messages correspond to points of a curve defined on a field of characteristic 3. Now the curves defined in characteristic 3 are the subject of major research and applications (cf. for example Jean-Luc Beuchat et al., “Algorithms and Arithmetic Operators for Computing the ηT Pairing in characteristic Three” IEEE Transactions on Computers, vol.57, No.11, November 2008 where a new hardware accelerator is proposed enabling the implementation of arithmetic on the finite field GF(397) that is isomorphic to GF(3)[X]/(X97+X12+2) where the X97+X12+2 is an irreducible polynomial in GF(3)[X]), and there is no non-probabilistic technique to process this case.
This means that it will be worthwhile to find a deterministic hash function for elliptic curves defined over GF(3n).